package com.mashibing.class16;

import java.util.HashSet;
import java.util.Stack;

// 深度优先遍历.
// 一条路没有走完 就直接走到底 (出现往回走的路)
// 走完了的话 就退回上一个节点 看看是否有其他的路可走.
// 如果有可走的路, 但是这条路以前走过, 直接忽略
// 如果有可走的路, 且这条路没有被走过, 则继续沿这条路走下去
public class Code02_DFS {
    public static void dfs(Node node) {
        if (node == null) {
            return;
        }
        // 准备一个栈, 用来存储走过的路径的各个节点.
        Stack<Node> stack = new Stack<Node>();
        // 准备一个登记表, 用来登记该节点是否已经走过.
        HashSet<Node> set = new HashSet<Node>();
        // 将入口节点加入 路径栈 和 登记表中.
        stack.add(node);
        set.add(node);
        System.out.println(node.value);// 入栈的时候 打印入栈的值.
        while (!stack.isEmpty()) {
            // 从栈中弹出一个节点.
            Node cur = stack.pop();
            // 遍历该站点的邻居.
            for (Node next : cur.nexts) {
                if (!set.contains(next)) { // 如果该邻居节点没有登记过, 说明该邻居节点没有走过, 则就走下去.
                    stack.push(cur);// 将for循环之上弹出的节点重新入栈Stack(路劲记录)
                    stack.push(next);// 将当前邻居节点压栈, 因为该节点在栈的上面, 下一次上层while循环弹栈的时候,会弹出邻居节点(next)
                    set.add(next); // 将邻居节点加入登记表中, 表示该邻居节点已经走过了.
                    System.out.println(next.value);// 打印当前令居节点 直接跳出当前for循环.
                    break;
                }
            }
        }
    }
}
